import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/1 16:32
 * @description 思路：A排序，B[i]加入到优先队列中，每次寻找大于堆顶的最小值，如果没有就用最左边的数代替， 田忌赛马
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {2, 0, 4, 1, 2}, nums2 = {1, 3, 0, 0, 2};
        solution.advantageCount(nums1, nums2);
    }

    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return b[1] - a[1];
        });
        int n = nums1.length;
        for (int i = 0; i < n; i++) {
            pq.add(new int[]{i, nums2[i]});
        }
        // 指向num1最小和最大的指针
        int left = 0, right = n - 1;
        int[] ans = new int[n];
        while (!pq.isEmpty()) {
            int[] temp = pq.poll();
            if (nums1[right] > temp[1]) {
                // A最大值 > B堆顶最大，
                ans[temp[0]] = nums1[right];
                right--;
            }else {
                // A最大值 <= B堆顶最大，用A最小值弥补
                ans[temp[0]] = nums1[left];
                left++;
            }
        }
        return ans;
    }
}
